package com.gwcloud.leetcode.offers;

/** 
* @ClassName   : Leetcode0330 
* @author      : ganwei 
* @date        : 2020年6月3日 
* @Description : TODO 
*/
public class Leetcode0330 {
	/**
	 * -解题思路
	 */
    public boolean verifyPostorder(int[] postorder) {
    	
    	return verify(postorder, 0, postorder.length-1);
    }
    public boolean verify(int[] postorder, int start, int end){
    	if(start >= end){
    		return true;
    	}
    	int index = end-1;
    	while(index >= start){
    		if(postorder[end] > postorder[index]){
    			break;
    		}
    		index--;
    	}
    	int mid = index;
    	while(index >= start){
    		if(postorder[end] < postorder[index]){
    			return false;
    		}
    		index--;
    	}
    	
    	return verify(postorder,start,mid) && verify(postorder, mid+1,end-1);
    }
    
    public static void main(String[] args){
    	Leetcode0330 l0330 = new Leetcode0330();
    	int[] nums = {1,6,3,2,5};
    	System.out.println(l0330.verifyPostorder(nums));
    }
}
